1. Field of the Invention
This invention relates to distributed file systems and, more particularly, to a method and apparatus for LRU stack synchronization between independent processors and a shared storage memory.
2. Description of the Related Art
In a distributed file system, a plurality of asynchronous processors, such as computers or workstations, are connected via a network. Each processor includes a local cache memory unit, which typically comprises a high-speed random access memory of from two to sixteen megabytes of storage capacity, and also includes a mass storage memory unit, typically a hard disk drive having from tens to perhaps hundreds of megabytes of storage capacity. The processors in the distributed file system typically need to share large blocks of data. Often the blocks of data are organized into pages, each of which contains four kilobytes of data. For efficient operation of the system, it is important to insure that the data blocks shared by the processors are quickly accessed and are consistent between the processors. Therefore, the processors are connected to a fast access, shared storage memory also referred to as a global cache. Although much data is shared across many processors, it is possible that none of the data used by any two processors will overlap. Therefore, the shared global cache memory typically has a capacity that is much larger than the sum of all the local cache memories in the processors.
The global cache memory contains data frequently accessed by the processors. It is faster for the processors to share data by obtaining it from the shared global cache memory rather than accessing the data from the hard disk drives of the appropriate processor. Moreover, it is easier to insure that data is consistent, meaning that all processors have the same value for the same shared data objects, by maintaining the data in the shared global cache memory. This consistency across processors is referred to as data coherency.
A least recently used (LRU) stack is maintained for the shared global cache memory and for each local cache memory associated with a processor. The LRU stack contains a list of data record-identifying indicia in the order of elapsed time since the last access, with the most recent at the top. For example, when a data record is first read into the cache memory, the indicia for that data record is placed at the top of the LRU stack. If a second data record is then read into the cache, then the first data record indicia is pushed down in the LRU stack and the indicia of the second data record becomes the top indicia in the stack.
If a data record already in a local cache is accessed, meaning that it is read or written over, then its indicia is moved to the top of the stack. As data records are accessed, their indicia are placed at the top of the LRU stack and the order of the stack changes. If a data record is not accessed for some time, eventually the data record indicia will be pushed down in the stack and will "fall off" the bottom of the stack. At that time, the data record is deleted from the local cache memory. If the associated processor requires the deleted data record, then the record must be obtained from the global cache memory or the appropriate hard drive and then will be placed back at the top of the stack. Similarly, the shared global cache memory maintains its LRU stack. As data records are brought into the global cache, they are placed at the top of the stack and old data records fall off the bottom of the stack and are deleted from the shared global cache memory.
When a processor writes to, or updates, its copy of a data record, it notifies the shared global cache memory of the write operation. Consequently, the LRU stack in the local cache memory and the LRU stack in the shared global cache memory are both updated at the same time. Before any other processor writes to a copy of that same data record in its respective local cache memory, that processor will check with the shared global cache memory, discover that the data record has been updated in the global cache, and will invalidate its copy of the data record and obtain a copy of the data record from the global cache. When a processor carries out a read operation on a data record and finds a copy of the data record in its local cache memory, referred to as a read hit, the processor will update the LRU stack associated with its local cache memory. One of the benefits of a distributed file system is the ability of the processors to independently carry out their tasks and only transfer data over the network when it is necessary for maintaining data coherency. It is not uncommon for a data record to be read many times by a processor without being written to. If every read hit in a local cache memory were followed by an LRU position update in the shared global cache memory, data coherency would be assured. Unfortunately, such a scheme has unacceptably large overhead and defeats many of the benefits of a multiple processor, distributed file system. Therefore, when a processor reads a data record from its local cache memory, it will update its LRU stack but will not notify the shared global cache memory of the read hit and therefore the LRU stack of the global cache will not be updated.
If a data record is read into both the shared global cache memory and a processor local cache memory, and is thereafter read many times by the processor but is not written to, then the data record may be at the top of the LRU stack for that local cache but might drop out of the LRU stack of the shared global cache. At the next data access by the processor, either a read operation or a write operation, the processor first will attempt to confirm with the shared global cache memory that its copy of the data record corresponds to the copy of the data record in the global cache. Because the data record will be missing from the global cache memory, the processor will assume its copy of the data record is invalid. Therefore, the processor will get the data record from the appropriate hard disk drive and will bring it back into both the shared global cache memory and the respective processor local cache memory. This invalidation of the local cache data record, even when the copy in local cache memory is actually valid, is referred to as false invalidation. Such false invalidations unnecessarily increase the time needed to carry out read and write operations at the local cache memory level. See, for example, U.S. Pat. No. 4,928,225 to McCarthy and "Increasing Hit Ratios in Second Level Caches and Reducing the Size of Second Level Storage" by L. Liu, IBM Technical Disclosure Bulletin, June 1984, pp. 334-337.
False invalidations occur either because the shared global cache memory is too small for the volume of data records used by the local cache memories or because the LRU stacks used in the global cache memory and local cache memories are not sufficiently coordinated, or synchronized. If the size of the global cache memory is less than the total effective size of the local cache memory, then false invalidations are inevitable. Conversely, a global cache memory that is as large as the total effective local cache memory does not guarantee a zero false invalidation rate because of the potential for unsynchronized LRU stack position of data indicia in the global and local cache memories. A larger shared global cache memory will reduce the false invalidation rate, but does so at the cost of additional memory. The memory size needed to eliminate false invalidations can be prohibitively expensive.
From the description above, it should be apparent that there is a need to reduce the number of false invalidations in a distributed file system without requiring excessively large shared global cache memory and LRU stack update rates. The present invention satisfies this need.